#include <iostream>
#include <queue>
#include <vector>
using namespace std;

struct Node
{
    int num; // 当前节点层数
    vector<int> route;
};

bool canPlace(Node q, int n)
{
    for (int j = 1; j < n; j++)
        if ((abs(n - j) == abs(q.route[j] - q.route[n])) || (q.route[j] == q.route[n]))
            return false;
    return true;
}

void nQueen(int n)
{
    queue<Node> Q;
    Node eol; // end of level，记录一层的结尾，用于进入下一层
    eol.num = -1;
    Q.push(eol);

    int curr_level = 1;
    Node curr_node;
    curr_node.num = 0;
    while (!Q.empty())
    {
        for (int k = 1; k <= n; k++)
        {
            Node q;
            q.num = curr_level;
            q.route.push_back(0);
            for (int i = 1; i < curr_level; i++)
                q.route.push_back(curr_node.route[i]);
            q.route.push_back(k);

            if (canPlace(q, curr_level))
                Q.push(q);
        }
        curr_node = Q.front();
        Q.pop();
        if (curr_node.num == -1)
        {
            curr_level++;
            Q.push(eol);
            curr_node = Q.front();
            Q.pop();
        }
        else if (curr_node.num == n)
        {
            for (int i = 1; i <= n; i++)
                cout << curr_node.route[i] << " ";
            cout << endl;
            break;
        }
    }
}

int main()
{
    cout << "请输入n皇后：n=";
    int n;
    cin >> n;
    nQueen(n);
    return 0;
}
